package org.apache.lucene.ocean.util;

import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

import org.apache.commons.lang.ObjectUtils;

/**
 * Maintains a sorted list of name value pairs that may also be accessed as a java.util.Map.
 * Internally the lookups occur using a binary search.
 * 
 * The class was created to provide the features of a map stored as a list to avoid using 
 * TreeMap which is harder to debug.  
 * 
 * @param <K>
 * @param <V>
 */
public class SortedListMap<K extends Comparable<K>,V> implements Map<K,V> {
  private ArrayList<SortedEntry<K,V>> entries;
  private transient Set<Map.Entry<K,V>> entrySet = null;
  transient volatile Set<K> keySet = null;
  transient volatile Collection<V> values = null;

  public SortedListMap() {
    entries = new ArrayList<SortedEntry<K,V>>();
  }
  
  public SortedListMap(int size) {
    entries = new ArrayList<SortedEntry<K,V>>(size);
  }

  public SortedListMap(Map<K,V> map) {
    this(map.size());
    putAll(map);
  }
  
  public String toString() {
    return entries.toString();
  }
  
  public Iterator<? extends Map.Entry<K,V>> iterator(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
    int fromPos = 0;
    if (fromKey != null) {
      fromPos = Collections.binarySearch(entries, new SortedEntry<K,V>(fromKey));
      if (fromPos >= 0) {
        if (!fromInclusive)
          fromPos++;
      } else if (fromPos < 0) {
        fromPos = -1 - fromPos;
      }
    }
    int toPos = entries.size()-1;
    if (toKey != null) {
      toPos = Collections.binarySearch(entries, new SortedEntry<K,V>(toKey));
      if (toPos >= 0) {
        if (!toInclusive)
          toPos--;
      } else if (toPos < 0) {
        toPos = -1 - toPos;
        toPos--;
      }
    }
    Iterator<SortedEntry<K,V>> iterator = entries.subList(fromPos, toPos+1).iterator();
    return new EntryIterator(iterator);
  }
  
  public ListIterator<? extends Map.Entry<K,V>> endListIterator() {
    return entries.listIterator(entries.size() - 1);
  }

  public ListIterator<? extends Map.Entry<K,V>> listIterator() {
    return entries.listIterator();
  }

  public ListIterator<? extends Map.Entry<K,V>> listIterator(int index) {
    return entries.listIterator(index);
  }

  private Map.Entry<K,V> removeMapping(Map.Entry<K,V> toRemove) {
    int pos = Collections.binarySearch(entries, new SortedEntry<K,V>((K) toRemove.getKey()));
    if (pos >= 0) {
      SortedEntry<K,V> entry = entries.get(pos);
      if (entry.value.equals(toRemove.getValue())) {
        entries.remove(pos);
        return entry;
      }
    }
    return null;
  }

  public static class SortedEntry<K extends Comparable<K>,V> implements Map.Entry<K,V>, Comparable<SortedEntry<K,V>> {
    private K key;
    private V value;

    private SortedEntry(K key, V value) {
      this.key = key;
      this.value = value;
    }
    
    public String toString() {
      String keyStr = null;
      if (key == null) keyStr = "";
      else keyStr = key.toString();
      String valueStr = null;
      if (value == null) valueStr = "";
      else valueStr = value.toString();
      return keyStr+"->"+value;
    }
    
    public K setKey(K key) {
      K oldKey = this.key;
      this.key = key;
      return oldKey;
    }

    public V setValue(V value) {
      V oldValue = this.value;
      this.value = value;
      return oldValue;
    }

    public K getKey() {
      return key;
    }

    public V getValue() {
      return value;
    }

    private SortedEntry(K key) {
      this.key = key;
    }

    public int compareTo(SortedEntry<K,V> other) {
      return key.compareTo(other.key);
    }
  }

  public void putAll(Map<? extends K,? extends V> m) {
    entries.ensureCapacity(m.size());
    for (Iterator<? extends Map.Entry<? extends K,? extends V>> i = m.entrySet().iterator(); i.hasNext();) {
      Map.Entry<? extends K,? extends V> e = i.next();
      put(e.getKey(), e.getValue());
    }
  }

  /**
   * public Set<K> keySet() { Set<K> set = new HashSet<K>(entries.size());
   * for (SortedEntry<K,V> entry : entries) { set.add(entry.key); } return set; }
   */
  // public Set<Map.Entry<K,V>> entrySet() {
  // Set<Map.Entry<K,V>> set = new HashSet<Map.Entry<K,V>>(entries);
  // return set;
  // }
  public boolean isEmpty() {
    return entries.size() == 0;
  }

  public void clear() {
    entries.clear();
  }

  public int size() {
    return entries.size();
  }

  private int getPos(K key) {
    int pos = Collections.binarySearch(entries, new SortedEntry<K,V>(key));
    if (pos < 0)
      pos = -1 - pos;
    return pos;
  }

  public boolean containsValue(Object value) {
    for (SortedEntry<K,V> entry : entries) {
      boolean b = ObjectUtils.equals(value, entry.value);
      if (b)
        return true;
    }
    return false;
  }

  public boolean containsKey(Object key) {
    int pos = Collections.binarySearch(entries, new SortedEntry<K,V>((K) key));
    return pos >= 0;
  }

  public K lastKey() {
    if (entries.size() == 0)
      return null;
    return entries.get(entries.size() - 1).key;
  }

  public V lastValue() {
    if (entries.size() == 0)
      return null;
    return entries.get(entries.size() - 1).value;
  }

  public V put(K key, V value) {
    V oldValue = null;
    int pos = Collections.binarySearch(entries, new SortedEntry<K,V>(key));
    if (pos >= 0) {
      oldValue = entries.get(pos).value;
      entries.set(pos, new SortedEntry<K,V>(key, value));
      return oldValue;
    }
    if (pos < 0)
      pos = -1 - pos;
    entries.add(pos, new SortedEntry<K,V>(key, value));
    return null;
  }

  private SortedEntry<K,V> getEntry(Object key) {
    int pos = Collections.binarySearch(entries, new SortedEntry<K,V>((K) key));
    if (pos >= 0) {
      return entries.get(pos);
    } else {
      return null;
    }
  }

  public V get(int index) {
    return entries.get(index).value;
  }

  public V get(Object key) {
    int pos = Collections.binarySearch(entries, new SortedEntry<K,V>((K) key));
    if (pos >= 0) {
      return entries.get(pos).value;
    } else {
      return null;
    }
  }

  public V remove(Object key) {
    assert key != null;
    int pos = Collections.binarySearch(entries, new SortedEntry<K,V>((K) key));
    if (pos >= 0) {
      SortedEntry<K,V> entry = entries.get(pos);
      entries.remove(pos);
      return entry.value;
    }
    return null;
  }

  public void add(K key, V value) {
    int pos = getPos(key);
    entries.add(pos, new SortedEntry<K,V>(key, value));
  }

  private abstract class SortedListIterator<E> implements Iterator<E> {
    private Iterator<SortedEntry<K,V>> iterator;

    public SortedListIterator() {
      iterator = entries.iterator();
    }
    
    public SortedListIterator(Iterator<SortedEntry<K,V>> iterator) {
      this.iterator = iterator;
    }

    protected Map.Entry<K,V> nextEntry() {
      return iterator.next();
    }

    public void remove() {
      iterator.remove();
    }

    public boolean hasNext() {
      return iterator.hasNext();
    }
  }

  private class ValueIterator extends SortedListIterator<V> {
    public V next() {
      return nextEntry().getValue();
    }
  }

  private class KeyIterator extends SortedListIterator<K> {
    public K next() {
      return nextEntry().getKey();
    }
  }

  private class EntryIterator extends SortedListIterator<Map.Entry<K,V>> {
    private EntryIterator() {}
    
    private EntryIterator(Iterator<SortedEntry<K,V>> iterator) {
      super(iterator);
    }
    
    public Map.Entry<K,V> next() {
      return nextEntry();
    }
  }

  // Subclass overrides these to alter behavior of views' iterator() method
  Iterator<K> newKeyIterator() {
    return new KeyIterator();
  }

  Iterator<V> newValueIterator() {
    return new ValueIterator();
  }

  Iterator<Map.Entry<K,V>> newEntryIterator() {
    return new EntryIterator();
  }

  public Set<K> keySet() {
    Set<K> ks = keySet;
    return (ks != null ? ks : (keySet = new KeySet()));
  }

  private class KeySet extends AbstractSet<K> {
    public Iterator<K> iterator() {
      return newKeyIterator();
    }

    public int size() {
      return entries.size();
    }

    public boolean contains(Object o) {
      return containsKey(o);
    }

    public boolean remove(Object o) {
      return SortedListMap.this.remove(o) != null;
    }

    public void clear() {
      SortedListMap.this.clear();
    }
  }

  public Collection<V> values() {
    Collection<V> vs = values;
    return (vs != null ? vs : (values = new Values()));
  }

  private class Values extends AbstractCollection<V> {
    public Iterator<V> iterator() {
      return newValueIterator();
    }

    public int size() {
      return SortedListMap.this.size();
    }

    public boolean contains(Object o) {
      return containsValue(o);
    }

    public void clear() {
      SortedListMap.this.clear();
    }
  }

  public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es = entrySet;
    return (es != null ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet()));
  }

  private class EntrySet extends AbstractSet/* <Map.Entry<K,V>> */{
    public Iterator/* <Map.Entry<K,V>> */iterator() {
      return newEntryIterator();
    }

    public boolean contains(Object o) {
      if (!(o instanceof Map.Entry))
        return false;
      Map.Entry<K,V> e = (Map.Entry<K,V>) o;
      SortedEntry<K,V> candidate = getEntry(e.getKey());
      return candidate != null && candidate.equals(e);
    }

    public boolean remove(Object o) {
      return removeMapping((Map.Entry<K,V>) o) != null;
    }

    public int size() {
      return SortedListMap.this.size();
    }

    public void clear() {
      SortedListMap.this.clear();
    }
  }

  /**
   * public Collection<V> values() { List<V> values = new ArrayList<V>(entries.size());
   * for (SortedEntry<K,V> entry : entries) { values.add(entry.value); } return
   * values; }
   */
}
